package haxe.util;

import haxe.util.Compare;
import haxe.util.SortedCollection;

class SortedArray<T> extends SortedCollection<T>
{
	private var _a:Array<T>;
	private 
	public function new( c:Comparator<T> )
	{
		super(c);
		_a = new Array();
	}
	
	public function add(o:T)
	{
		super.add(o);
		if ( _a.length != 0 )
		{
			if ( comp( o, _a[0] ) < 0 )
				_a.unshift(o);
			else if ( comp( o, _a[ _a.length - 1 ] ) > 0 )
				_a.push(o);
			else
			{
				//var i:Int = gInd(o);
				_a.insert( getInd(o), o );
			}
		}else
			_a.push(o);
	}
	
	public function remove():T
	{
		return _a.shift();
	}
	
	public function removeFirst():T
	{
		return remove();
	}
	
	public function removeLast():T
	{
		return _a.pop();
	}
	
	public function getLast():T
	{
		return _a[_a.length-1];
	}
	
	public function getFirst():T
	{
		return _a[0];
	}
	
	public function toString():String
	{
		return "SortedArray";
	}
	
	private function getInd(o:T):Int
	{
		var e:Int = _a.length-1;
		var b:Int = 0;
		var i:Int = ( e + b )>>1;
		var c:Int;
		while( e > b + 1 ) 
		{
			c = comp( o, _a[i] );
			if ( c > 0 )
				b = i;
			else if ( c < 0 )
				e = i;
			else
				return i;
			i = ( e + b )>>1;
		}
		return
		if ( comp( o, _a[b] ) > 0  )
		{
			if ( comp( o, _a[e]) < 0)
				e;
			else
				e+1;
		}else 
			b;
	}
}